package com.zhaopin.theswordreferstooffer;

/**
 * @author yin.peide
 * @date 2021-06-25 15:16
 * 面试题34: 丑数
 */
public class Offer34 {

    public static void main(String[] args) {


        long l1 = System.currentTimeMillis();

        //好的时间复杂度
        System.out.println(getUglyNumber(10000));
        long l2 = System.currentTimeMillis();
        System.out.println(l2 - l1);

        //后面这个时间复杂度相当差
        System.out.println(getUglyNum(1000));

        long l3 = System.currentTimeMillis();
        System.out.println(l3 - l2);
    }

    /**
     * 时间复杂度低 空间复杂度高，典型的空间换时间
     *
     * @param index
     * @return
     */
    public static int getUglyNumber(int index) {
        if (index <= 0) {
            return 0;
        }
        //初始化三个指向三个潜在成为最小丑数的位置
        int p2 = 0, p3 = 0, p5 = 0;
        int[] result = new int[index];
        result[0] = 1;
        for (int i = 1; i < index; i++) {
            result[i] = Math.min(result[p2] * 2, Math.min(result[p3] * 3, result[p5] * 5));
            if (result[i] == result[p2] * 2) {
                p2++;
            }
            //为了防止重复需要三个if都能够走到
            if (result[i] == result[p3] * 3) {
                p3++;
            }

            //为了防止重复需要三个if都能够走到
            if (result[i] == result[p5] * 5) {
                p5++;
            }

            //为了防止重复需要三个if都能够走到


        }
        return result[index - 1];
    }

    /**
     * 思考简单的方法 判断是否是丑数 时间复杂度高
     *
     * @param n
     * @return
     */
    public static boolean isUglyNum(int n) {
        while (n % 2 == 0) {
            n = n / 2;
        }

        while (n % 3 == 0) {
            n = n / 3;
        }

        while (n % 5 == 0) {
            n = n / 5;
        }
        if (n == 1) {
            return true;
        } else {
            return false;
        }
    }


    public static int getUglyNum(int index) {
        if (index <= 0) {
            return 0;
        }

        //一直增长的实际的丑数
        int number = 0;
        //满足条件是丑数才跟着系数涨的数
        int uglyFound = 0;
        while (uglyFound < index) {
            number++;

            if (isUglyNum(number)) {
                ++uglyFound;
            }
        }

        return number;
    }

}
